package com.demo.datastructure.queue;

/**
 * @description:
 * @author: ljr
 * @time: 2021/4/28 13:23
 */
public class ArrayQueue {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k == 0) return null;
        int[] results = new int[nums.length-k+1];
        int numlength = 0;
        ArrayCircularQueue queue = new ArrayCircularQueue(k);
        for(int i = 0; i < nums.length; i++){
            if(queue.enqueue(nums[i])){ continue; }
            results[numlength++] = queue.getMax();
            queue.dequeue();
        }
        return results;
    }

    private static class ArrayCircularQueue{

        private final Integer[] args;

        private final int capacity;

        private int head;

        private int tail;

        private int max;

        private int size;

        public ArrayCircularQueue(int capacity) {
            this.capacity = capacity;
            args = new Integer[capacity];
        }

        public boolean enqueue(int value) {
            if(size == capacity) return false;
            args[tail] = value;
            tail = (tail + 1)%capacity;

            if(size == 0){
                max = value;
            }else{
                max = max < value ? value : max;
            }
            size++;
            return size != capacity;
        }

        public Integer getMax() {
            return max;
        }


        public Integer dequeue() {
            if(size-- == 0) return  null;
            int value = args[head];
            args[head] = null;
            head = (head + 1)%capacity;
            if(max == value){
                if(capacity == 1){
                    return value;
                }

                if(capacity == 2){
                    max = args[(size+2)%capacity];
                    return value;
                }

                int i = 0;
                for(Integer num : args){
                    if(num == null){ continue; }
                    if(i++ == 0) {
                        max = num;
                    }else{
                        max = max < num ? num : max;
                    }
                }
            }
            return value;
        }
    }

    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue();
        int[] nums = new int[]{1,-1};
        int[] newnums = arrayQueue.maxSlidingWindow(nums,1);
        for(int num : newnums){
            System.out.println(num);
        }
    }
}
